package 动态规划;

public class 解码方法 {
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n+1];
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            dp[i+1] = s.charAt(i)== '0' ? 0 : dp[i];
            if (i>0 && (s.charAt(i-1)=='1' || (s.charAt(i-1)=='2' && s.charAt(i)<='6')))
                dp[i+1]+=dp[i-1];
        }
        return dp[n];
    }
}
